<html>
<head>
	<meta charset="UTF-8">
	<meta content="IE=edge" http-equiv="X-UA-Compatible">
	<meta content="initial-scale=1.0, maximum-scale=1.0, user-scalable=no, width=device-width" name="viewport">
	<title>3833：[Poi2014]Solar lamps</title>
	<!-- css -->
	<link href="../css/base.min.css" rel="stylesheet">
	<link href="../css/project.min.css" rel="stylesheet">
	
	<!-- favicon -->
	<!-- ... -->
</head>
<body class="page-brand">
	<header class="header header-transparent header-waterfall ui-header">
		<ul class="nav nav-list pull-left">
			<li>
				<a data-toggle="menu" href="#menu">
					<span class="icon icon-lg">menu</span>
				</a>
			</li>
		</ul>
		<a class="header-logo header-affix-hide margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Solar lamps</a>
		<span class="header-logo header-affix margin-left-no margin-right-no" data-offset-top="213" data-spy="affix">[Poi2014]Solar lamps</span>
	</header>
	<nav aria-hidden="true" class="menu" id="menu" tabindex="-1">
		<div class="menu-scroll">
			<div class="menu-content">
				<a class="menu-logo" href="../index.html">BZOJ离线题库</a>
				<ul class="nav">
					<li>
						<a class="waves-attach" data-toggle="collapse" href="#problems">题目</a>
						<ul class="menu-collapse collapse in" id="problems">
							<li>
								<a class="waves-attach" href="../index.html">主页</a>
							</li>
							<li>
								<a class="waves-attach" href="../list.html">题目列表</a>
							</li>
						</ul>
					</li>
					<li>
						<a class="collapsed waves-attach" data-toggle="collapse" href="#about">关于</a>
						<ul class="menu-collapse collapse" id="about">
							<li>
								<a class="waves-attach" href="../about.html">关于此项目</a>
							</li>
						</ul>
					</li>
					
				</ul>
			</div>
		</div>
	</nav>
	<main class="content">
		<div class="content-header ui-content-header">
			<div class="container">
				<h1 class="content-heading">
                [Poi2014]Solar lamps                </h1>
                <p>时间限制：80s&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;  空间限制：128MB</p>			</div>
		</div>
		<div class="container">
			<section class="content-inner margin-top-no">
				<div class="row">
					<div class="col-lg-13 col-md-13">
						<div class="card margin-bottom-no">
							<div class="card-main">
								<div class="card-inner">
									
                                <h3>题目描述</h3><p><div>Byteasar has a large and pretty garden. As he would like to be able to appreciate its beauty even after dusk, he installed lamps across the garden.</div>
<div>The lamps are directional, i.e., they illuminate only a certain angle, common to them all. Moreover, Byteasar has aligned them so that they all face the same direction. Last but not least, these are solar lamps, i.e., they come with solar panels but no batteries, strangely enough! You might think the panels are thus useless, and each lamp will require electricity at night, but not quite: A lamp will produce light if a sufficient number of lamps illuminate it.</div>
<div>By now, Byteasar has even come up with an order he is going supply the lamps with electricity, thus turning them on. For simplicity, we number the lamps from 1 to n in this order, i.e., the lamp no. i is supplied with electricity at time i. The only thing left for Byteasar (and you, of course!) is to figure out when exactly each lamp will start emitting light. Help Byteasar by writing a program that will determine the answer to this question.</div>
<div></div>
<div><span style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">Byteasar有一个美丽的大花园。因为他喜欢在黄昏后欣赏花园的美丽，他在花园中安装了许多盏灯。</span></div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">这些灯是有方向的，它们只会朝一个确定的夹角内发光。而且，Byteasar把它们安放地很整齐，所以它们都面朝同一个方向。</div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">这些灯都是太阳能灯，它们使用的是太阳能而不是电能。第i盏灯会发光当且仅当至少Ki盏灯照到了它或者它通了电。</div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">现在，Byteasar将按1到n的顺序依次给每盏灯通电，即在第i个时刻给第i盏灯通电。</div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">最后，Byteasar想知道每盏灯在哪一个时刻开始发光，请写一个程序回答这个问题。</div>
<div></div>
<p></p></p><hr/><h3>输入格式</h3><p><div>The first line of the standard input contains a single integer N(1&lt;=N&lt;=200 000): the number of lamps Byteasar installed. In the second line of input, there are four integers X1,Y1,X2,Y2(-10^9&lt;=Xi,Yi&lt;=10^9,(Xi,Yi&lt;&gt;(0,0) ), separated by single spaces, that describe the area illuminated by every lamp. Namely, if there is a lamp located at the point (x,y), then it illuminates the area (together with its edge) within the smaller of the two angles formed by two rays that both originate at (x,y) such that the i-th (for i=1,2) ray passes through(x+Xi,y+Yi). This angle is always smaller than 180 degrees.</div>
<div>The n input lines that follow specify the locations of the lamps: the i-th such line contains two integers Xi,Yi(-10^9&lt;=Xi,Yi&lt;=10^9), separated by a single space, that indicate that the lamp no. &nbsp; is located at the point (Xi,Yi). You may assume that no two lamps share their location.</div>
<div>The last line of the input contains N integers K1,k2&hellip;Kn(1&lt;=Ki&lt;=N), separated by single spaces, that signify that if the lamp no. i is in the area illuminated by at least Ki other lamps, then it will start emitting light as well.</div>
<div></div>
<div><span style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">第一行包含1个整数N(1&lt;=N&lt;=200 000)，表示灯数。</span></div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">第二行包含4个整数X1,Y1,X2,Y2(-10^9&lt;=Xi,Yi&lt;=10^9,(Xi,Yi&lt;&gt;(0,0))，描述每盏灯的照明范围。比如，有盏灯位于(x,y)，则它会照亮在(x,y)到(x+X1,y+Y1)这条射线，(x,y)到(x+X2,y+Y2)这条射线之间(包括边界)的区域，这个角度在[0&deg;,180&deg;)之间。</div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">接下来N行每行两个整数Xi,Yi(-10^9&lt;=Xi,Yi&lt;=10^9)，表示第i盏灯的位置，保证没有两盏灯重合。</div>
<div style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">最后一行包含N个整数K1,K2&hellip;Kn(1&lt;=Ki&lt;=N)，表示第i盏灯至少需要被几盏灯照到才会发光。</div>
<div></div>
<div></div>
<p></p></p><hr/><h3>输出格式</h3><p><div>Your program should print out to the standard output a single line with &nbsp; integers T1&hellip;Tn, separated by single spaces. The number Ti should be the time when the lamp no. i starts producing light.</div>
<div><span style="font-family: Helvetica, 'Microsoft Yahei', verdana; font-size: 14px; line-height: 23px;">输出一行N个整数T1...Tn，其中Ti表示第i盏灯开始发光的时刻。</span></div>
<p></p></p><hr/><h3>样例输入</h3><pre>5
3 1 1 3
2 1
1 4
3 4
5 6
5 2
1 2 1 3 2</pre><hr/><h3>样例输出</h3><pre>1 2 1 2 5</pre><hr/><h3>提示</h3><p><div>Explanation: At time 1 Byteasar powers on the lamp 1, which also causes the lamp 3 to produce light. Once the lamp 2 is powered on, the lamp 4 begins to emit light (being illuminated by lamps 1, 2, and 3).</div>
<div></div>
<p></p></p><hr/><h3>题目来源</h3><p>鸣谢 Claris</p>
								</div>
							</div>
						</div>
					</div>
				</div>
				
				
			</section>
		</div>
	</main>

	<div class="fbtn-container">
		<div class="fbtn-inner">
			<a class="fbtn fbtn-lg fbtn-brand-accent waves-attach waves-circle waves-light waves-effect" data-toggle="dropdown" aria-expanded="true"><span class="fbtn-text fbtn-text-left">Menu</span><span class="fbtn-ori icon">apps</span><span class="fbtn-sub icon">close</span></a>
			<div class="fbtn-dropup">
				<a class="fbtn fbtn-brand waves-attach waves-circle waves-light waves-effect" href="../list.html" target="_self"><span class="fbtn-text fbtn-text-left">题目列表</span><span class="icon">menu</span></a>
				<a class="fbtn fbtn-green waves-attach waves-circle waves-effect" href="../index.html" target="_self"><span class="fbtn-text fbtn-text-left">返回主页</span><span class="icon">home</span></a>
				<a class="fbtn waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/submitpage.php?id=3833" target="_blank"><span class="fbtn-text fbtn-text-left">提交代码</span><span class="icon">send</span></a>
				<a class="fbtn fbtn-orange waves-attach waves-circle waves-effect" href="http://www.lydsy.com/JudgeOnline/wttl/wttl.php?pid=3833" target="_blank"><span class="fbtn-text fbtn-text-left">试题讨论</span><span class="icon">chat</span></a>
				
			</div>
		</div>
	</div>

	<!-- js -->
	<script src="../js/jquery.min.js"></script>
	<script src="../js/base.min.js"></script>
	<script src="../js/project.min.js"></script>
</body>
</html>